package algorithm.heap;


import util.GsonUtil;

import java.util.*;

/**
 * leetcode : https://leetcode.com/problems/top-k-frequent-elements/description/
 * Difficulty : Medium
 *
 * 给一个数组，求其中出现频率K大的数字
 * 举栗：
 * Input : [1,1,1,2,2,3]
 * Output : [1,2]
 *
 * 1、
 * 第一个想到的解是构建HashMap来统计数字出现频率。
 * 至于优先队列，可以使用Java提供的 PriorityQueue，也可以自己写一个简单的PQ
 * （PS: 建议自己写）
 *
 * 2、
 * 还有一个思路：Bucket sort（桶排序）
 * 思路参考：
 * https://leetcode.com/problems/top-k-frequent-elements/discuss/81602/Java-O(n)-Solution-Bucket-Sort
 * https://www.cnblogs.com/kkun/archive/2011/11/23/2260267.html
 *
 *
 * @Author Antony
 * @Since 2018/7/9 18:42
 */
public class TopKFrequentElements {

    public static void main(String[] args) {
        int[] arr = new int[]{1,1,1,2,2,3};
        topKFrequent(arr, 2);

        int[] ints = topKFrequent_bucket(arr, 2);
        System.out.println(GsonUtil.toJson(ints));
    }


    /**
     * 桶排序思路：建立一个数组。数组的下标表示元素出现的次数。相同出现次数的数字被放到相应的桶中
     *           桶中维护一个链表。保存所有出现该次数的数字集合
     *           最后倒序数组，依次取出桶中的元素。
     *
     * 8ms, 99.6%
     * 40.2MB,  30.6%
     * @param nums
     * @param k
     * @return
     */
    public static int[] topKFrequent_bucket(int[] nums, int k) {
        // 统计数字频率
        Map<Integer, Integer> countMap = new HashMap<>();
        for(int num : nums){
            countMap.compute(num, (key,val) -> val==null ? 1 : val+1);
        }
        // 放入桶中
        List<Integer>[] bucket = new List[nums.length+1];
        for(Map.Entry<Integer, Integer> entry : countMap.entrySet()){
            int buckeyIdx=entry.getValue();
            List<Integer> numList = bucket[buckeyIdx];
            if(numList == null) {
                numList = new ArrayList<>();
            }
            numList.add(entry.getKey());
            bucket[buckeyIdx] = numList;
        }

        int[] res = new int[k];
        int resIdx = 0;
        out:
        for(int i=bucket.length-1; i>=0; i--){
            List<Integer> tmpList = bucket[i];
            if(tmpList==null){
                continue;
            }
            for(Integer n : tmpList){
                if(resIdx==k) break out;
                res[resIdx++] = n;
            }
        }
        return res;
    }


    /**
     * (beats 31.73% - 51ms)
     *
     * 思路，构建一个HashMap来统计每个数字出现的频率。
     * 剩下的工作就是TopK了，只不过是对Entry的TopK heap
     */
    public static List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap();  //key=num val=frequent
        for(int n : nums){
            map.compute(n, (key,val) -> (val==null? 1 : val+1));    //统计数字的出现频率
        }

        // 获取迭代器，迭代Entry构建小顶堆
        Iterator<Map.Entry<Integer, Integer>> itr = map.entrySet().iterator();
        Map.Entry<Integer, Integer>[] heap = new Map.Entry[k];
        for(int i=0; i<k&&itr.hasNext(); i++){
            Map.Entry<Integer, Integer> entry = itr.next();
            int childIndex = i;
            int parentIndex = (childIndex-1)/2;
            while(parentIndex >=0 && childIndex != 0 && heap[parentIndex].getValue() > entry.getValue()){
                heap[childIndex] = heap[parentIndex];
                childIndex = parentIndex;
                parentIndex = (parentIndex-1)/2;
            }
            heap[childIndex] = entry;
        }

        while(itr.hasNext()){
            Map.Entry<Integer, Integer> entry = itr.next();
            if(entry.getValue() > heap[0].getValue()){
                insertToHeap(heap, entry);
            }
        }

        List<Integer> result = new ArrayList<>(k);
        for(Map.Entry<Integer, Integer> entry : heap){
            result.add(entry.getKey());
        }

        return result;
    }

    // 入堆
    static void insertToHeap(Map.Entry<Integer,Integer>[] heap, Map.Entry<Integer, Integer> entry){
        int hole = 0;
        int lChild, rChild, minIndex, tmpVal;
        while(hole < heap.length){
            lChild = hole*2+1;
            rChild = hole*2+2;
            minIndex = hole;
            tmpVal = entry.getValue();
            if(lChild < heap.length && tmpVal > heap[lChild].getValue()){
                minIndex = lChild;
                tmpVal = heap[lChild].getValue();
            }
            if(rChild < heap.length && tmpVal > heap[rChild].getValue()){
                minIndex = rChild;
            }

            if(minIndex == hole){
                break;
            }else{
                heap[hole] = heap[minIndex];
                hole = minIndex;
            }
        }
        heap[hole] = entry;
    }
}
